Матч 413, Бесконечная последовательность (InfiniteSequence)

Дивизион 2, Уровень 3

Рассмотрим бесконечную последовательность А, определенную следующим образом:

A₀ = 1,

A_i = A_[i/p] + A_[i/q] , i ³ 1

По заданным n, p, q вычислить A_n.

Класс: InfiniteSequence

Метод: long long calc(long long n, int p, int q)

Ограничения: 0 £ n £ 10¹², 2 £ p, q £ 10⁹.

Вход. Целые значения n, p, q.

Выход. Значение A_n.

Пример входа

n	p	q
0	2	3
10000000	3	3
256	2	4

Пример выхода

1

32768

89

РЕШЕНИЕ

структуры данных – map, рекурсия

Вычислить все значения A_i (i = 0, 1, …, n) последовательности невозможно при помощи массива из-за ограничения n £ 10¹². Для запоминания результатов будем использовать структуру map: значение m[i] будет хранить A_i. Находим значение A_n, запоминая промежуточные результаты.

ПРОГРАММА

#include <cstdio>

#include <map>

using namespace std;

map<long long,long long> m;

class InfiniteSequence

{

public:

long long calc(long long n, int p, int q)

{

if (m[n]) return m[n];

if (!n) return 1;

return m[n] = calc(n/p,p,q) + calc(n/q,p,q);

}

};